package com.problem.leetcode;

/**
 * @author yanzhuoleo
 * @version V1.0
 * @Description: Problem23
 * @date 2018-01-05-下午8:12
 */

public class Problem23 {
    public  ListNode mergeKLists(ListNode[] lists) {

        if(lists.length <= 0) {
            return null;
        }

        return mergeKLists(lists, 0, lists.length - 1);
    }

    public  ListNode mergeKLists(ListNode[] lists, int begin, int end) {
        if (begin >= end) {
            return lists[begin];
        }

        int      middle = (begin + end) >> 1;
        ListNode left   = mergeKLists(lists, begin, middle);
        ListNode right  = mergeKLists(lists, middle + 1, end);
        return mergeTwoLists(left, right);
    }

    public  ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newListNode = new ListNode(-1);
        ListNode currentNode = newListNode;

        while (l2 != null && l1 != null) {
            if (l1.val >= l2.val) {
                currentNode.next = new ListNode(l2.val);
                l2 = l2.next;
            } else {
                currentNode.next = new ListNode(l1.val);
                l1 = l1.next;
            }
            currentNode = currentNode.next;
        }

        ListNode tmp = null;
        if (l2 != null) {
            tmp = l2;
        }

        if (l1 != null) {
            tmp = l1;
        }

        if (tmp != null) {
            while (tmp != null) {
                currentNode.next = new ListNode(tmp.val);
                currentNode = currentNode.next;
                tmp = tmp.next;
            }
        }
        return newListNode.next;
    }

    public class ListNode {
        int      val;
        ListNode next;

        ListNode(int x) { val = x; }
    }

}
